//产生数
#include <iostream>
#include <queue>
using namespace std;
const int MAXK=15;
int n,k;
int c;
struct NUM{
    char e[4]={0,0,0,0};
    int len=0;
    void read_from(int x){
        while(x>0){
            e[len++]=x%10;
            x=x/10;
        }
    }

    NUM clone(){
        NUM ret;
        for(int i=0;i<len;i++) ret.e[i]=e[i];
        ret.len=len;
        return ret;
    }
    int value(){
        return e[3]*1000+e[2]*100+e[1]*10+e[0];
    }
};
int x[MAXK+1],y[MAXK+1];
bool flag[10000];
queue<NUM> qu;
int main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++) cin>>x[i]>>y[i];
    NUM start;
    start.read_from(n);
    qu.push(start);
    flag[start.value()]=true;
    c++;
    while(!qu.empty()){
        NUM cur=qu.front();
        qu.pop();
        for(int i=1;i<=k;i++)
            for(int j=0;j<cur.len;j++)
            {
                if (cur.e[j]==x[i]){
                    NUM newnum=cur.clone();
                    newnum.e[j]=y[i];
                    int v=newnum.value();
                    //cout<<cur.value()<<':'<<x[i]<<"->"<<y[i]<<'='<<v<<endl;
                    if (!flag[v]){
                        c++;
                        qu.push(newnum);
                        flag[v]=true;
                    }
                }
            }
    }
    cout<<c;
}
